The field of this invention is cryptography. This invention relates to digital signature schemes, and in particular to schemes that are compatible with any escrowed encryption system. The scheme introduces a public key/private key system in which the public key is auto-certifiable and is effective only as a digital signature verification key, and is not effective at performing unescrowed encryptions of data. Furthermore, the private signing key in the system is not escrowed. If the public key is ever used to encrypt data then that data is auto-recoverable by trusted authorities. The invention relates to cryptosystems implemented in software, but is also applicable to cryptosystems implemented in hardware. In particular the invention can be employed as the signature and authentication component in conjunction with escrowed encryption schemes.
Public Key Cryptosystems (PKC""s) allow secure communications between two parties who have never met before. The notion of a PKC was put forth in (W. Diffie, M. Hellman, xe2x80x9cNew directions in cryptographyxe2x80x9d, IEEE Transactions on Information Theory, 22, pages 644-654, 1976). This communication can take place over an insecure channel. In a PKC, each user possesses a public key E and a private key D. E is made publicly available by a key distribution center, also called certification authority (CA), after the registration authority verifies the authenticity of the user (its identification, etc.). The registration authority is part of the certification authority. D is kept private by the user. E is used to encrypt messages, and only D can be used to decrypt messages. It is computationally impossible to derive D from E. To use a PKC, party A obtains party B""s public key E from the key distribution center. Party A encrypts a message with E and sends the result to party B. B recovers the message by decrypting with D. The key distribution center is trusted by both parties to give correct public keys upon request. In the same paper by Diffie and Hellman the notion of a digital signature scheme was also proposed. A digital signature scheme allows a user to digitally xe2x80x9csignxe2x80x9d a message using the private key known only to the user, to prove that the message comes from the user. To sign a message M, the user computes a signature using the private key D. The signature can then be verified using the public key E. A PKC and digital signature scheme based on the difficulty of computing discrete logarithms was published in (T. ElGamal, xe2x80x9cA Public-Key Cryptosystem and a Signature Scheme Based on Discrete Logarithmsxe2x80x9d, CRYPTO ""84, pages 10-18, Springer-Verlag, 1985). 
Since the present invention discloses a method for generating, publishing, and employing public key systems based upond a digital signature algorithm which is based on the problem of computing discrete logarithms, we will cite relevant prior art dealing with discrete log based signature schemes. The first space efficient digital signature scheme based on discrete logarithms is the Digital Signature Algorithm (U.S. Pat. No. 5,231,668). DSA gets its security from the difficulty of computing discrete logs modulo the prime p, where p is at least 512 bits in size. It also gets its security from the difficulty of computing discrete logs in a cyclic subgroup of order q, where q is a 160 bit prime divisor of pxe2x88x921. DSA is novel in that the signatures that it outputs are 320 bits in length. Nyberg and Rueppel disclosed a set of ElGamal based variants that provide for message recovery (K. Nyberg, R. Rueppel, xe2x80x9cMessage Recovery for Signature Schemes Based on the Discrete Logarithm Problem, Eurocrypt ""94, pages 182-193, 1994). The message recovery feature allows the message to be recovered from the signature itself, hence the message need not be sent along with the signature. Another important feature of digital signature schemes is blindability (D. Chaum, xe2x80x9cBlind Signatures for Untraceable Paymentsxe2x80x9d, CRYPTO ""82, pages 199-203). A scheme is blindable if it is possible for Alice to obtain a Bob""s signature on a message of her choice such that Bob remains oblivious as to what he is signing and what the resulting signature is. In (D. Chaum, T. Pedersen, xe2x80x9cWallet Databases with Observersxe2x80x9d, CRYPTO ""92, pages 89-105) a blindable scheme based on ElGamal is disclosed. A good overview of digital signature security is described in (S. Goldwasser, S. Micali, R. Rivest, xe2x80x9cA digital Signature Scheme Secure Against Adaptive Chosen Message Attacksxe2x80x9d, SIAM J. Comput., vol. 17, n. 2, pages 281-308, 1988).
In the U.S. Patent Document entitled xe2x80x9cAuto-Escrowable and Auto-Certifiable Cryptosystemsxe2x80x9d (by Young and Yung), a public key cryptosystem was disclosed that has the following properties. Users of the system can generate a public/private key pair and a certificate of recoverability. This certificate of recoverability can be used to both recover the private key by the escrow authorities, and verify that the private key is recoverable. The present invention draws many of its ideas from the Auto-Escrowable and Auto-Certifiable key escrow solution but concentrates on signature keys that have the feature that encryptions using the public verification key are auto-recoverable. Other methods for conducting key escrow are U.S. Pat. Nos. 5,276,737, and 5,315,658 which are due to Micali (1994). In these patents Micali discloses a Fair Public Key Cryptosystem (FPKC) which is based on the work of P. Feldman (28th annual FOCS). The FPKC solution is not as efficient in terms of use as Auto-Escrowable and Auto-Certifiable Cryptosystems. Furthermore, it has been shown that the Fair RSA PKC does not meet certain needs of law enforcement (J. Kilian, F. Leighton, xe2x80x9cFair Cryptosystems Revisitedxe2x80x9d, CRYPTO ""95, pages 208-221, Springer-Verlag, 1995, see also U.S. Pat. No. 5,647,000 to Leighton), since a shadow public key cryptosystem can be embedded within it. A shadow public key system is a system that can be embedded in a key escrow system that permits conspiring users to conduct untappable communications. Kilian and Leighton disclose a Fail-safe Key Escrow system. This system has the drawback that it requires users to engage in a multi-round protocol in order to generate public/private key pairs. Other key escrow systems with similar inneficiencies are by De Santis et al., Walker and Winston (TIS), and the IBM SecureWay document. A xe2x80x9cFraud-Detectable Alternative to Key-Escrow Proposalsxe2x80x9d based on ElGamal has been described in (E. Verheul, H. van Tilborg, xe2x80x9cBinding ElGamal: A Fraud-Detectable Alternative to Key-Escrow Proposalsxe2x80x9d, Eurocrypt ""97, pages 119-133, Springer-Verlag, 1997). This system provides for session level key recoverability, and makes no provision for preventing users from encrypting messages prior to using the Binding ElGamal system. Hence, it permits conspiring criminals to conduct untappable communications. Both Binding ElGamal and the Auto-Escrowable and Auto-Certifiable Cryptosystems solutions employ the use of non-interactive zero-knowledge proofs. More specificly, they employ the Fiat Shamir heuristic which is disclosed in (A. Fiat, A. Shamir, xe2x80x9cHow to Prove Yourself: Practical Solutions to Identification and Signature Problemsxe2x80x9d, CRYPTO ""86, pages 186-194, Springer-Verlag, 1987). An overview of key escrow schemes appears in (D. Denning, D. Branstad, xe2x80x9cA Taxonomy for Key Escrow Encryption Systems,xe2x80x9d Communications of the ACM, v. 39, n. 3, 1996). In (N. Jefferies, C. Mitchell, M. Walker, xe2x80x9cA Proposed Architecture for Trusted Third Party Servicesxe2x80x9d, Cryptography: Policy and Algorithms, LNCS 1029, Springer, 1996) and (R. Anderson, xe2x80x9cThe GCHQ Protocol and Its Problemsxe2x80x9d, Eurocrypt ""97, pages 134-148, Springer-Verlag, 1997) a trusted third party approach to escrow is described where the trusted third parties of the participating users are involved in every session key establishment stage, and hence provides for another encumbersome solution as well. Such solutions are described in the TIS patent (U.S. Pat. Nos. 5,557,346, 5,557,765, and 5,640,454 to Lipner et al.) and the IBM patents (U.S. Pat. Nos. 5,796,830 and 5,815,573 to Johnson et al.). Adding time limits to keys is given in (U.S. Pat. No. 5,633,928 to Lenstra et al.).
The primary problem with implementing a digital signature scheme suitable for a national usage is that very often the public verifying key can be used as a public encryption key, and the corresponding private signing key can be used as a private decryption key. For law enforcment purposes it is therefore necessary to escrow the signing private keys. But this implies that law enforcement has the capability of forging signatures of users, and also impersonating users in interactive identification protocols. There is no legitimate reason that law enforcement should have this capability. Hence, what is needed is a public and private key system that is usable for digital signatures but not for public key encryptions. This problem was stated informally in a request for comments that was published in the Federal Register (xe2x80x9cAnnouncing Plans to Revise Federal Information Processing Standard 186, Digital Signature Standardxe2x80x9d, vol. 62, n. 92, Federal Register, pages 26293-26294, May 13, 1997).
We will now give reasons why existing digital signatures schemes fail due to shadow public key vulnerabilities. Consider the ElGamal digital signature algorithm (T. ElGamal, xe2x80x9cA Public-Key Cryptosystem and a Signature Scheme Based on Discrete Logarithmsxe2x80x9d, CRYPTO ""84, pages 10-18, Springer-Verlag, 1985). In ElGamal, the public key is y=gx mod p, where x is the private signing key. Here g is a public generator modulo the public prime p. Suppose that y is an escrowed public key. This insures that it can""t be used for unescrowed encryptions. But, now the escrow authorities can forge signatures. Suppose that y isn""t escrowed. Then signatures can""t be forged by the escrow authorities, but y now consititues a shadow public key. Note that the same situation occurs with DSA, the Schnorr digital signature algorithm, and the ElGamal variants of Nyberg and Rueppel (K. Nyberg, R. Rueppel, xe2x80x9cMessage Recovery for Signature Schemes Based on the Discrete Logarithm Problemxe2x80x9d, Eurocrypt ""94, pages 182-193, Springer-Verlag, 1994).
Now consider the RSA digital signature algorithm (U.S. Pat. No. 4,405,829 to Rivest et al.). Recall that in RSA n is the product of two large primes p and q. e is a public value such that gcd(e,(pxe2x88x921)(qxe2x88x921))=1. e and n are the user""s public verification keys, and the inverse of e mod (pxe2x88x921)(qxe2x88x921) is the user""s private signing key. It is simple enough to revise RSA key generation to preclude shadow public key abuse. It remains to consider the aspects of the digital signature algorithm. Suppose that n is escrowed. It follows that the escrow authorities can forge signatures. Suppose that n is not escrowed. It is clear then that the escrow authorities can""t forge, but n is a shadow public key. Thus RSA is subject to the same dichotomy as the discrete log based systems. This abuse applies also to the other algorithms based on the difficulty of factoring. For example, consider Esign (U.S. Pat. No. 4,625,076 to Okamoto et al.). In Esign, n=p2q. It is possible to do RSA like encryptions and decryptions using such a modulus.
In Fiat-Shamir (U.S. Pat. No. 4,748,668 to Shamir et al.), n is the product of two primes and none of the users know the factorization of n. To generate a public key, a user generates k different quadratic residues v1, v2, . . . , vk modulo n. This vector is the public key. The scheme therefore succumbs to the following shadow public key attack. The user""s agree on a value (or a set of values) g to be the base for the group Zn* (hopefully it generates a large subgroup). To generate v1 for a public key, a malicious user chooses w at random and sets v1=g2w mod n. Thus, v1 is a quadratic residue, and a shadow public key for ElGamal mod n. The shadow private key is 2w.
To the best of our knowledge all digital signature algorithms aside from Okamoto ""92 (T. Okamoto, xe2x80x9cProvably Secure and Practical Identification Schemes and Corresponding Signature Schemesxe2x80x9d, CRYPTO ""92, pages 31-53, Springer-Verlag, 1993) fail immediately when viewed in light of the needs for a satisfactory digital signature infrastructure. Recall that in Okamoto, the public verification key is v=g1{circumflex over ( )}(xe2x88x92s2)*g2{circumflex over ( )}(xe2x88x92s2) mod p. The symbol {circumflex over ( )} denotes exponentiation, hence a{circumflex over ( )}b is a raised to the b power. Here g1 and g2 have order q modulo the public prime p. The values for g1, g2, and q are also public. The private key is (s1,s2). Both s1 and s2 are chosen randomly modulo q. Okamoto is based on the representation problem modulo p.
To sign a message m in Okamoto, we choose two values r1 and r2 randomly mod q. We then compute e=H(g1{circumflex over ( )}(r1)*g2{circumflex over ( )}(r2) mod p,m). Here H is a one-way hash function. We then compute y1=r1+es1 mod q and y2=r2+es2 mod q. The signature is the triple (e,y1,y2). To verify the signature we check that e=H(g1{circumflex over ( )}(y1)*g2{circumflex over ( )}(y2)*ve mod p,m).
At first sight it seems like Okamoto is a good candidate for the setting of a national PKI for signatures, which is to be used alongside an escrowed PKI. For, suppose we don""t escrow v. Then the escrow authorities can""t forge signatures. But, then we need to insure that v cannot be used as a shadow public key. In fact, we need to show that any key based on the representation problem with g1 and g2 can""t be used as an encryption public key. To see this, note that the quantity g1{circumflex over ( )}(y1)*g2{circumflex over ( )}(y2)*ve mod p is in fact just g1{circumflex over ( )}(r1)*g2{circumflex over ( )}(r2) mod p. Hence, a modular exponentiation with two bases is displayed during signature verification. Now suppose that there is a public key encryption algorithm for public keys with representations using two bases. Since Okamoto is extendible to three or more bases, maybe there is no encryption algorithm if the representation uses three bases, or four bases, etc.
In fact, there is a public key algorithm that uses public keys based on the representation problem with any number of bases. To public key encrypt a message m using v as in Okamoto, we do the following.
1. choose k randomly from Zq 
2. a=g1k mod p
3. b=vk mod p
4. c=g2k*m mod p
5. the ciphertext of m is (a,b,c)
To decrypt we compute:
1. axe2x80x2=a{circumflex over ( )}(xe2x88x92s1) mod p which equals g1{circumflex over ( )}(xe2x88x92s1*k) mod p
2. bxe2x80x2=b/axe2x80x2 mod p which equals g2{circumflex over ( )}(xe2x88x92s2*k) mod p
3. m=c/(bxe2x80x2{circumflex over ( )}(xe2x88x921/s2)) mod p
Note that unlike in ElGamal encryptions, the ciphertext is a triple. This algorithm can be easily extended to handle representations using more bases. The ciphertext is an (m+1)-tuple if m bases are used in the representation of v. Thus, Okamoto and it""s exentions using more bases fails to meet the requirements of the system that is needed.
In the pending U.S. patent application entitled xe2x80x9cAuto-Recoverable and Auto-Certifiable Cryptosystem with Unescrowed Signing Keysxe2x80x9d (A. Young, M. Yung, Ser. No. 08/878,189), a solution was presented that attempted to solve this problem. However, the primary embodiment of that solution, and it""s variants, have a drawback that was not addressed. Recall that the solution proposed a three key system which involved a signing private key, a decryption private key, and a public key suitable for public key encryptions and signature verifications. The private signing key and the public verification key are used in a digital signature algorithm that is very similar to the ElGamal digital signature scheme, and its variants. The problem with the system is that in the primary embodiment and it""s variants, a signature involves publishing a value which can be used as a shadow public key. For example, in the primary embodiment, the value a=H(m)(g1/Y)xe2x88x92t mod 2q is computed as the first part of the signature on m. Yet this quantity can be used as a shadow public key in an ElGamal-like public key cryptosystem where t is the unescrowed decryption key. To see this, note that all users have access to H(m), so they can compute the public key w=a/H(m) mod 2q. The value (g1/Y)xe2x88x921 can be used as the base gxe2x80x3 (or generator, if you will) of Z2q. The key pair is thus ((w, gxe2x80x3, 2q),t), which is an ElGamal public/private key pair in the group Z2q . All each malicious collaborator needs to do is publish a single signature to a bulletin board, and retain the unescrowed decryption key. This is a major drawback, since the bulletin board then serves as a shadow public key database, and having it taken down by law-enforcement can be argued to be a violation of the first ammendment in court by the collaborators, in the event that law-enforcment tries to take the bulleten board down. The present invention solves this problem by introducing a digital signature algorithm where no shadow public keys are displayed through the digital signatures that are computed. Indeed, what is needed is a new signature scheme that is secure and does not provide public keys which can be used for unescrowed public key encryption, especially in the context of an escrowed PKI.
Key Recovery Infrastructure with Unescrowed Signatures
The present invention discloses a digital signature mechanism that, unlike all known schemes mentioned above, cannot be used for untappable wire communications. Thus it provides simultaneously for an unescrowed signature scheme and an escrowed encryption scheme. The Auto-Escrowable and Auto-Certifiable solution provides an efficient way to implement a public key infrastructure, thereby allowing privacy for users. The present invention builds on that solution and provides the added functionality of authentication capabilities needed in key escrow environments. Thus users of the present invention can verify the authenticity and origin of message senders.
In order to provide for the above objective the present invention introduces a new idea in cryptography. The present invention introduces a public key which can be used to verify digital signatures but cannot be used to encrypt data in a way that prevents escrow authorities from decrypting the data. The public key has the usual property that it is intractable to derive the corresponding private key from the public key. The present invention also has the property that the escrow authorities and CA""s are unable to forge the signatures of users of the system.
The present invention consists of a key certification process, a signing process, a signature verification process, and a key (or information) recovery process. The key certification process can be broken down into two functions which are key generation, and key verification. In the key generation process, a public key, the corresponding private signing key, and information proving that the keys were generated properly is output. In the key certification process, the user transmits this information to the certification authorities (CA) (or registration authority, which is often part of the CA). The certification authority takes this information, processes it, and decides to either publish the public key or not. If the verification information indicates that the keys were generated properly using the key generation algorithm, the certification authority publishes the users public key. Otherwise, the users request for certification is rejected, and the CA may take subsequent action which may include informing the user of this. In the prefered embodiment, public keys that are properly verified by the CA are digitaly signed by the CA and a digital certificate from this information is formed. A public key together with a CA""s signature on a string that contains the public key constitutes a certified public key. It is the public key and/or the digital certificate that is made available to other users by the CA. User""s sign messages and verify messages in the same manner as in typically digital signature schemes. In the recovery process, information that is encrypted using the public signature verification key of a user is decrypted using information that was sent to the CA during key certification. This may be done without any special authorization, since the public key is only supposed to be used for digital signature verification (another infrastructure should be devoted to ensuring confidentiality, if confidentiality is needed). The method by which the CA certifies and publicizes keys may differ according to the numerous methods available in the art. There are many ways for the CA to act, the ways we adopt in the current description is merely illustrative and there are other variations that are known to the skilled in the art whose implementations does not differ from the current invention.
The present invention is useful in any environment that requires messages to be verifiably authentic. Such environments arise in law enforcement nationally and internationally, in the business sector, in secure file systems, etc. The present invention may involve recovery agents. The present invention is also directly extendable to authentication that is conducted via the use of interactive identification protocols by methods known to those skilled in the art.
The present invention is robust with respect to any underlying technology since it can be implemented in both hardware and software. When implemented in software it can be easily scrutinized to insure that it functions as desired and to insure that it does not compromise the security of its users. The software implementation allows for fast and easy dissemination of the invention, since it can be disseminated in source code form over diskettes or over a computer communication network. The invention does not require changes in communication protocols used in typical unescrowed PKI""s (e.g., session key establishment, key distribution, secure message transmission, etc.). The invention is therefore compatible with typical PKI""s. The present invention thus provides a very efficient way of allowing for digital signatures.